/*
 * 背包放物品
 * https://www.lintcode.com/problem/125/leaderboard
 * */
public class Solution {
    public static int backPackII(int m, int[] A, int[] V) {
        int row = A.length + 1;
        int col = m + 1;
        int[][] array = new int[row][col];
        for (int i = 0; i < col; i++) {
            array[0][i] = 0;
        }
        for (int i = 1; i < row; i++) {
            array[i][0] = 0;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (A[i - 1] > j) {
                    array[i][j] = array[i - 1][j];
                } else {
                    array[i][j] = max(array[i - 1][j], array[i - 1][j - A[i - 1]] + V[i - 1]);
                }
            }
        }
        return array[row - 1][col - 1];
    }

    public static int backPackII2(int m, int[] A, int[] V) {
        int row = A.length + 1;
        int col = m + 1;
        int[] array = new int[col];
        for (int i = 0; i < col; i++) {
            array[i] = 0;
        }
        for (int i = 1; i < row; i++) {
            int[] temp = array.clone();
            for (int j = 0; j < col; j++) {
                if (j == 0) {
                    array[j] = 0;
                } else {
                    if (A[i - 1] > j) {
                        array[j] = temp[j];
                    } else {
                        array[j] = max(temp[j], temp[j - A[i - 1]] + V[i - 1]);
                    }
                }
            }
        }
        return array[col - 1];
    }
}